# To change this template, choose Tools | Templates
# and open the template in the editor.
#
# todo
#   +function to create sudokus

__author__="martin"
__date__ ="$04.04.2010 12:38:24"

import scipy
import sys

size=9
ok=1
nok=0

def create_sudoku(num_fields):
    mat=scipy.zeros([size, size])
    n=0
    x=scipy.random.randint(size)
    y=scipy.random.randint(size)
    mat[y, x]=scipy.random.randint(size)
    mat=solve_sudoku(mat)
    while n < (size**2-num_fields):
        x=scipy.random.randint(size)
        y=scipy.random.randint(size)
        if mat[y, x]!=0:
            mat[y, x]=0
            n+=1
    return mat

def control_row(mat, y, x):
    res=1
    for yi in xrange(0, size):
        if yi!=y:
            if mat[yi, x]==mat[y, x]:
                res=0
    return res

def control_column(mat, y, x):
    res=1
    for xi in xrange(0, size):
        if xi!=x:
            if mat[y, xi]==mat[y, x]:
                res=0
    return res

def control_quadrat(mat, y, x):
    res=1
    xbegin=int(x/3)*3
    xend=xbegin+3
    ybegin=int(y/3)*3
    yend=ybegin+3
    for xi in xrange(xbegin, xend):
        for yi in xrange(ybegin, yend):
            if xi!=x or yi!=y:
                if mat[yi, xi]==mat[y, x]:
                    res=0
    return res

def control_mat(mat):
    res=ok
    x=0
    y=0
    while res and x < size and y < size:
        loesungen=range(1, size+1)
        if mat[y, x]== 0.0:
            loesungen=check_row(mat, y, x, loesungen)
            loesungen=check_column(mat, y, x, loesungen)
            #print loesungen
            loesungen=check_quadrat(mat, y, x, loesungen)
            #print loesungen
            if len(loesungen) < 1:
                #print x,y,mat[y, x],loesungen
                res=nok
        else:
            if res:
                res=control_row(mat, y,x)
                if res:
                    res=control_column(mat, y, x)
                    if res:
                        res=control_quadrat(mat, y, x)
        x+=1
        if x>=size:
            y+=1
            x=0
    return res

def error_msg(text):
    print text

def save_sudoku(filename, mat):
    try:

        file=open(filename, "w")
    except:
        error_msg("could not open file!")
        return nok
    for y in xrange(0, size):
        h=str(int(mat[y, 0]))
        for x in xrange(1, size):
            h+=","+str(int(mat[y, x]))
        h+="\n"
        file.write(h)
    file.close()
    return ok

def load_sudoku(filename):
    mat=scipy.zeros([size, size])
    try:

        file=open(filename)
    except:
        error_msg("file not found!")
        return mat
    i=0
    for line in file:
        numbers=line.strip().split(",")
        j=0
        for e in numbers:
            mat[i, j]=int(e)
            j+=1
        i+=1
    return mat

def check_row(mat, i, j, loesungen):
    n=0
    for n in range(0, size):
        e=mat[n, j]
        if e in loesungen:
            loesungen.remove(e)
    return loesungen

def check_column(mat, i, j, loesungen):
    for n in range(0, size):
        e=mat[i, n]
        if e in loesungen:
            loesungen.remove(e)
    return loesungen

def check_quadrat(mat, i, j, loesungen):
    if 0 <= i <= 2:
        irange=[0, 1, 2]
    elif 3<= i <=5:
        irange=[3, 4, 5]
    else:
        irange=[6, 7, 8]
    if 0 <= j <= 2:
        jrange=[0, 1, 2]
    elif 3<= j <=5:
        jrange=[3, 4, 5]
    else:
        jrange=[6, 7, 8]
    for n in irange:
        for m in jrange:
            e=mat[n, m]
            if e in loesungen:
                loesungen.remove(e)
    return loesungen


def solve_sudoku(omat=scipy.zeros([size, size])):
    #mat=load_sudoku(fname)
    #print mat
    mat=omat.copy()
    loesungen=range(1, size+1)
    solved=0
    index_l=0
    index_s=0
    min_i=0
    min_j=0
    mat_saved=list([])
    while not solved:
        solved=1
        simple=0
        min_l=9
        delete_branch=0
        #print mat
        for i in range(0, size):
            for j in range(0, size):
                loesungen=range(1, size+1)
                if mat[i, j]== 0:
                    solved=0
                    loesungen=check_row(mat, i, j, loesungen)
                    loesungen=check_column(mat, i, j, loesungen)
                    loesungen=check_quadrat(mat, i, j, loesungen)

                    if len(loesungen)==1:
                        #print loesungen,
                        simple=1
                        mat[i, j]=loesungen[0]
                    if len(loesungen)==0:
                        delete_branch=1
                        #print i, j, mat[i, j], mat


                            
                            
                    if 1< len(loesungen) < min_l:
                        min_i=i
                        min_j=j
                        min_l=len(loesungen)
                        index_l=0
        if delete_branch:
            index_s=len(mat_saved)-1
            #print mat_saved
            ok=1
            if (len(mat_saved[index_s]["loesungen"]) <= 1):
                mat_saved.pop()
                index_s=len(mat_saved)-1

            if index_s >= 0:
                #print index_s, mat_saved[index_s]

                if len(mat_saved[index_s]["loesungen"]) > 1:
                    l=mat_saved[index_s]["loesungen"][0]
                    mat_saved[index_s]["loesungen"].remove(l)
                    mat=mat_saved[index_s]["mat"]
                    min_i=mat_saved[index_s]["min_i"]
                    min_j=mat_saved[index_s]["min_j"]
                    mat[min_i, min_j]=mat_saved[index_s]["loesungen"][0]
                #print index_s,mat_saved[index_s]
                simple=0
                index_l+=1
        elif not simple and not delete_branch and not solved:
            #solved=0
            loesungen=range(1,10)
            loesungen=check_row(mat, min_i, min_j, loesungen)
            loesungen=check_column(mat, min_i, min_j, loesungen)
            loesungen=check_quadrat(mat, min_i, min_j, loesungen)
            if len(loesungen) > 0:
                #index_s+=1
                d=dict([])
                d["mat"]=mat.copy()
                d["min_i"]=min_i
                d["min_j"]=min_j
                d["loesungen"]=loesungen

                mat_saved.append(d)
                
                mat[min_i, min_j]=loesungen[0]
    return mat

def test():
    mat=load_sudoku("sudoku1.txt")
    mat=solve_sudoku(mat)
    print mat
    mat=load_sudoku("sudoku2.txt")
    mat=solve_sudoku(mat)
    print mat
    mat=load_sudoku("sudoku_106.txt")
    mat=solve_sudoku(mat)
    print mat

def main(fname):
    mat=solve_sudoku(fname)
    print mat

if __name__ == "__main__":
    if sys.argv[1]=="-test":
        test()
    else:
        main(sys.argv[1])

